#include<iostream>
#include<string>
using namespace std;

struct TreeNode {
	int val;
	TreeNode* left;
	TreeNode* right;
	TreeNode() : val(0), left(nullptr), right(nullptr) {}
	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
	TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};

class Solution {
public:

    void sumNumbers(TreeNode* root, string num, int& sum)
    {
        if (root == nullptr)
        {
            return;
        }
        if (root->left == nullptr && root->right == nullptr)
        {
            num += to_string(root->val);
            sum += stoi(num);
            return;
        }
        num += to_string(root->val);
        sumNumbers(root->left, num, sum);
        sumNumbers(root->right, num, sum);
    }
    int sumNumbers(TreeNode* root) {
        string num;
        int sum = 0;
        sumNumbers(root, num, sum);
        return sum;
    }
};


class Solution2 {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root, 0);
    }

    int dfs(TreeNode* root, int presum)
    {
        if (root == nullptr)return 0;
        presum = presum * 10 + root->val;
        if (root->left == nullptr && root->right == nullptr)
            return presum;
        int ret = 0;
        int leftsum = dfs(root->left, presum);
        int rightsum = dfs(root->right, presum);
        ret = leftsum + rightsum;
        return ret;
    }
};